package com.lsa.skienna.challenge.chap9.the110901_Bicoloring;

import java.io.InputStream;
import java.io.PrintStream;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static final int MAXV = 200;
	static boolean processed[] = new boolean[MAXV];
	static boolean discovered[] = new boolean[MAXV];
	static int parent[] = new int[MAXV];
	static int label[] = new int[MAXV];

	static boolean isBicoralable = true;

	static void bfsMark(graph g, int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		int i, v;
		q.add(start);
		discovered[start] = true;
		label[start] = 0;
		while (!q.isEmpty()) {
			v = q.poll();
			process_vertex(v);
			processed[v] = true;
			for (i = g.degree[v] - 1; i >= 0; i--) {
				int u = g.edges[v][i];
				if (!discovered[u]) {
					q.add(u);
					label[u] = invertLabel(label[v]);
					discovered[u] = true;
					parent[u] = v;
				}
			}
		}
	}
	
	static void bfsCheck(graph g, int start) {
		Queue<Integer> q = new LinkedList<Integer>();
		int i, v;
		q.add(start);
		discovered[start] = true;
out:		
		while (!q.isEmpty()) {
			v = q.poll();
			process_vertex(v);
			processed[v] = true;
			for (i = g.degree[v] - 1; i >= 0; i--) {
				int u = g.edges[v][i];
				if (!discovered[u]) {
					q.add(u);
					if (!checkLabels(g, u)){
						isBicoralable = false;
						break out;
					}
					discovered[u] = true;
					parent[u] = v;
				}
			}
		}
	}

	static boolean checkLabels(graph g, int v) {
		int vLabel = label[v];
		for (int i = g.degree[v] - 1; i >= 0; i--) {
			if (label[g.edges[v][i]] == vLabel) {
				return false;
			}
		}
		return true;
	}

	static int invertLabel(int label) {
		return label == 0 ? 1 : 0;
	}

	static boolean valid_edge(int v) {
		return true;
	}

	static void initialize_search(graph g, boolean initLabels) {
		isBicoralable = true;
		for (int i = 0; i < g.nvertices; i++) {
			processed[i] = discovered[i] = false;
			parent[i] = -1;
			if (initLabels) label[i] = -1;
		}
	}

	static void process_vertex(int v) {
	}

	static void process_edge(graph g, int x, int y) {
		System.out.printf("processed edge (%d,%d)\n", x, y);
		g.nedges = g.nedges + 1;
	}

	static public void main(String[] args) {
		InputStream in = System.in;
		PrintStream out = System.out;
		process(in, out);
	}

	public static void process(InputStream in, PrintStream out) {
		graph g = new graph();
		Scanner sc = new Scanner(in);
		while (g.read_graph(false, sc)) {
			initialize_search(g, true);
			bfsMark(g, 0);
			initialize_search(g, false);
			bfsCheck(g, 0);
			if (isBicoralable) {
				out.println("BICOLORABLE.");
			}
			else {
				out.println("NOT BICOLORABLE.");
			}
			g = new graph();
		}
	}

}

class graph {
	static final int MAXV = Main.MAXV;
	static final int MAXDEGREE = Main.MAXV * 2;

	public int edges[][] = new int[MAXV + 1][MAXDEGREE];
	public int degree[] = new int[MAXV + 1];
	public int nvertices;
	public int nedges;

	graph() {
		nvertices = nedges = 0;
		for (int i = 1; i <= MAXV; i++)
			degree[i] = 0;
	}

	boolean read_graph(boolean directed, Scanner sc) {
		int x, y;
		nvertices = sc.nextInt();
		if (nvertices > 0) {
			int m = sc.nextInt();
			for (int i = 1; i <= m; i++) {
				x = sc.nextInt();
				y = sc.nextInt();
				insert_edge(x, y, directed);
			}
		}
		return nvertices > 0;
	}

	void insert_edge(int x, int y, boolean directed) {
		if (has_edge(x, y)) return;
		if (degree[x] > MAXDEGREE)
			System.out.printf(
					"Warning: insertion (%d, %d) exceeds max degree\n", x, y);
		edges[x][degree[x]] = y;
		degree[x]++;
		if (!directed)
			insert_edge(y, x, true);
		else
			nedges++;
	}
	
	boolean has_edge(int x, int y) {
		for (int i = 0; i < degree[x]; i++) {
			if (edges[x][i] == y) {
				return true;
			}
		}
		return false;
	}

	void print_graph() {
		for (int i = 0; i < nvertices; i++) {
			System.out.printf("%d: ", i);
			for (int j = degree[i] - 1; j >= 0; j--)
				System.out.printf(" %d", edges[i][j]);
			System.out.printf("\n");
		}
	}
}